//: [Previous](@previous)

/*:
 ### LeetCode上第86号问题：Partition List
 ```
 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 你应当保留两个分区中每个节点的初始相对位置。
 示例:
 输入: head = 1->4->3->2->5->2, x = 3
 输出: 1->2->2->4->3->5
 ```
 */

var list = SinglyLinkedList(arr: [1,4,3,2,5,2])

// 使用两个虚拟结点
func Solution(_ head: ListNode?, _ x: Int) -> ListNode? {
    
    var left: ListNode = ListNode(-1)
    let leftstart: ListNode = left
    var right: ListNode = ListNode(-1)
    let rightstart: ListNode = right
    
    var temp = head
    while temp != nil {
        if temp!.val < x {
            left.next = temp
            temp = temp?.next
            left = left.next!
            left.next = nil
        } else {
            right.next = temp
            temp = temp?.next
            right = right.next!
            right.next = nil
        }
    }
    
    left.next = rightstart.next
    
    return leftstart.next
}

print(list)
list.head = Solution(list.head, 3)
print(list)


//: [Next](@next)
